#!/usr/bin/env python2
# coding: utf-8

from __future__ import print_function
import lab5, random, timeit
from lab5 import test_func


#print('{0:>20s}:{1:^30s}:{2:^30s}:{3:^30s}:{4:^30s}'.format('n  ', 'random read, head (ms)', 'random read, tail (ms)',
#      'random write, head (ms)', 'random write, tail (ms)'))
#for k in xrange(3, 9):
#    x = 10 ** k
#    lst = range(x)  # gotta be careful with this
#    i = 0
#    L_idx_access_head = timeit.Timer('i = lst[1]', 'from __main__ import i, lst')
#    L_idx_access_tail = timeit.Timer('i = lst[{0:d}]'.format(len(lst) - random.randint(2, 10)),
#                                     'from __main__ import i, lst')
#    L_idx_assign_head = timeit.Timer('lst[1] = i', 'from __main__ import i, lst')
#    L_idx_assign_tail = timeit.Timer('lst[{0:d}] = i'.format(len(lst) - random.randint(2, 10)),
#                                     'from __main__ import i, lst')
#    print('{0:>18d}  '.format(x), end='')
#    print('{0:^30.7f}'.format(L_idx_access_head.timeit(number=1000)), end='')
#    print('{0:^30.7f}'.format(L_idx_access_tail.timeit(number=1000)), end='')
#    print('{0:^30.7f}'.format(L_idx_assign_head.timeit(number=1000)), end='')
#    print('{0:^30.7f}'.format(L_idx_assign_tail.timeit(number=1000)))
#print()

#lst = [random.randint(-(2 ** 31), 2 ** 31 - 1) for i in xrange(int(5e+6))]

def kth_ord_sort():
    k = 1000  # XXX: hardcoded K value
    lst.sort()
    return lst[k - 1]

#test_func(kth_ord_sort, iterations=1)
#print()

#lst = [random.randint(-(2 ** 31), 2 ** 31 - 1) for i in xrange(int(5e+6))]
lst = [random.randint(1, 99) for i in xrange(20)]
del i

def randomized_select(A=lst, k=(499 % len(lst)), left=0, right=(len(lst) - 1)):
    """
    Return k'th lowest element in A.

    Modifies input list.
    """
    print('{0}(): k={1} left={2} right={3}'.format('randomized_select', k, left, right))
    if left == right:
        return A[left]
    m = randomized_partition(A, left, right)
    if m is None or not (left <= m <= right):
        print('m is bad (', m, ')', sep='')
    if k == m:
        return A[m]
    elif k < m:
        return randomized_select(A, k, left, right - m)
    return randomized_select(A, abs(m - k), left + m + 1, right)

def randomized_partition(A, left=0, right=(len(lst) - 1)):
    """
    Quicksort's partition.
    """
    print('{0}(): left={1} right={2}'.format('randomized_partition', left, right))
    swap = random.randint(left, right)
    A[left], A[swap] = A[swap], A[left]
    x = A[left]
    i = left
    for j in xrange(left + 1, right + 1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i], A[left] = A[left], A[i]
    return i

#test_func(randomized_select)
print(lst)
print(sorted(lst))
print(sorted(lst)[3])
print(randomized_select(A=lst, k=3))
